/**
 * 
 */
package com.gwcloud.leetcode.offers;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName   : Leetcode0130 
 * @author      : ganwei 
 * @date        : 2020年5月31日
 * @Description : Leetcode0130 机器人的运动范围
 */
public class Leetcode0130 {
	/**
	 * -深度优先遍历
	 */
    public int movingCount(int m, int n, int k) {
    	Queue<Coordinate> q = new LinkedList<Coordinate>();
    	q.offer(new Coordinate(0,0));
    	int count = 0;
    	boolean[][] visited = new boolean[m][n];
    	visited[0][0] = true;
    	while(!q.isEmpty()){
    		Coordinate c = q.poll();
    		count++;
    		//上
    		if(c.x - 1 >= 0 && c.x - 1 < m && numDigitSum(c.x - 1, c.y, k) && !visited[c.x - 1][c.y]){
    			q.offer(new Coordinate(c.x - 1,c.y));
    			visited[c.x - 1][c.y] = true;
    			
    		}
    		//下
    		if(c.x + 1 >= 0 && c.x + 1 < m && numDigitSum(c.x + 1, c.y, k) && !visited[c.x + 1][c.y]){
    			q.offer(new Coordinate(c.x + 1,c.y));
    			visited[c.x + 1][c.y] = true;
    		}
    		//左
    		if(c.y - 1 >= 0 && c.y - 1 < n && numDigitSum(c.x, c.y - 1, k) && !visited[c.x][c.y - 1]){
    			q.offer(new Coordinate(c.x, c.y - 1));
    			visited[c.x][c.y - 1] = true;
    		}
    		//右
    		if(c.y + 1 >= 0 && c.y + 1 < n && numDigitSum(c.x, c.y + 1, k) && !visited[c.x][c.y + 1]){
    			q.offer(new Coordinate(c.x, c.y + 1));
    			visited[c.x][c.y + 1] = true;
    		}
    	}
	
    	return count;
    }
    
    /**
     * -数位和
     */
    public boolean numDigitSum(int i, int j, int k){
    	int sum = 0;
    	while(i != 0){
    		sum += i % 10;
    		i = i/10;
    	}
    	while(j != 0){
    		sum += j % 10;
    		j = j/10;
    	}
    	return sum <= k;
    }
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    	
    }
}

class Coordinate{
	public int x;
	public int y;
	public Coordinate(int x, int y){
		this.x = x;
		this.y = y;
	}
}
